import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class TreeNode1 {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode1() {}
    TreeNode1(int val) { this.val = val; }
    TreeNode1(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if(root.val>key){
            root.left=deleteNode(root.left,key);
        }else if(root.val<key){
            root.right=deleteNode(root.right,key);
        }else{
            if(root.right==null){
                return root.left;
            }else if(root.left==null){
                return root.right;
            }else{
                TreeNode cur=root.right;
                TreeNode prev=cur;
                while (cur!=null){
                    prev=cur;
                    cur=cur.left;
                }
                prev.left=root.left;
                root=root.right;
            }
        }
        return root;
    }



















    public int maxProfit(int[] prices) {
        int len=prices.length;
        int[] dp=new int[len];
        for(int i=1;i<len;i++){
            int max=Integer.MIN_VALUE;
            int price=prices[i];
            for(int j=0;j<i;j++){
                int prev=j-2>=0?dp[j-2]:0;
                max=Math.max(max,prev+price-prices[j]);
            }
            dp[i]=Math.max(dp[i-1],max);
        }
        return dp[len-1];
    }




















    public int largestInteger(int num) {
        String str=String.valueOf(num);
        char[] ch=str.toCharArray();
        for(int i=0;i<ch.length;i++){
            for(int j=i+1;j<ch.length;j++){
                if(ch[j]-ch[i]>0&&(ch[j]-ch[i])%2==0){
                    char c=ch[j];
                    ch[j]=ch[i];
                    ch[i]=c;
                }
            }
        }
        return Integer.parseInt(String.valueOf(ch));
    }

















    public boolean checkTree(TreeNode root) {
        if(root==null){
            return false;
        }
        return root.val==root.left.val+root.right.val;
    }




















    public int[] numberOfLines(int[] widths, String s) {
        int x=0;
        int y=0;
        for(int i=0;i<s.length();i++){
            int value=widths[s.charAt(i)-'a'];
            y+=value;
            if(y>100){
                x++;
                y=value;
            }
        }
        return new int[]{x,y};
    }
}
